| 7.21.1 [15] <7.9> When performing computations on sparse matrices, latency in the memory hierarchy becomes much more of a factor. Sparse matrices lack the spatial locality in the data stream typically found in matrix operations. As a result, new matrix representations have been proposed. One the earliest sparse matrix representations is the Yale Sparse Matrix Format. It stores an initial sparse m×n matrix, M in row form using three onedimensional arrays. Let R be the number of nonzero entries in M. We construct an array A of length R that contains all nonzero entries of M (in lefttoright toptobottom order). We also construct a second array IA of length m + 1 (i.e., one entry per row, plus one). IA(i) contains the index in A of the first nonzero element of row i. Row i of the original matrix extends from A(IA(i)) to A(IA(i+1)–1). The third array, JA, contains the column index of each element of A, so it also is of length R. Consider the sparse matrix X below and write C code that would store this code in Yale Sparse Matrix Format. Row 1 [1, 2, 0, 0, 0, 0] Row 2 [0, 0, 1, 1, 0, 0] Row 3 [0, 0, 0, 0, 9, 0] Row 4 [2, 0, 0, 0, 0, 2] Row 5 [0, 0, 3, 3, 0, 7] Row 6 [1, 3, 0, 0, 0, 1] | |
| View Solution | |
| << Back | Next >> |